package com.chapter2.sort;

/** 
 * @ClassName: QuickSort 
 * @Description: 快速排序
 * 快速排序的平均时间复杂度为O(1.39NlgN)，最坏的情况下，也就是如果已经是一个完全顺序的数组，时间复杂度为O(1/2N^2)，所以为了保证效率，在快排之前需要对他进行洗牌
 * 
 * 本身是在冒泡排序的基础之上改进，冒泡排序是把最大值冒泡一样冒出来，而快速排序是把切分标记值利用多次比较冒出来。
 * 快速排序最坏的情况之下就相当于一个冒泡排序的步骤
 * 
 * @author minjun minjun@bw30.com
 * @date 2015-2-13 下午11:14:02 
 *  
 */
public class QuickSort extends AbstractSort{
	
	private Shuffle shuffle;
	

	public QuickSort() {
		shuffle=new ShuffleImpl();
	}

	@Override
	public void sort(int[] array) {
		//对数组洗牌，如果不洗牌，那么糟糕的输入会使得写法良好的快速排序崩溃（StackOverflowError栈内存溢出）
		//实际演示情况，本机上测试，输入1w个顺序数组（顺序数组是快速排序最怕的，时间复杂度为降低到二次方），如果不进行“洗牌”，那么就会 出现栈内存溢出错误
		shuffle.randomShuffle(array);
		//排序
		sort(array,0,array.length-1);
	}

	/** 
	* @Title: sort 
	* @Description: 排序
	* @param @param array
	* @param @param i
	* @param @param j    设定文件 
	* @return void    返回类型 
	* @throws 
	*/ 
	protected void sort(int[] array, int i, int j) {
		if(i>=j) return;
		//切分数组
		int k=partition(array,i,j);
		//将左边排序
		sort(array,i,k-1);
		//将右边排序
		sort(array, k+1, j);
	}

	/** 
	* @Title: partition 
	* @Description:切分
	* @param @param array    设定文件 
	* @return void    返回类型 
	* @throws 
	*/ 
	private int partition(int[] array,int start,int end) {
		int i=start,j=end+1;
		
		while(true){
			//左边递增，直到有大于标记值的停止，如果一路都小于标记值，那么在到达最后一个索引时停止
			while(less(array[++i],array[start])){
				if(i>=end) break;
			}
			//右边递减，直到有小于标记值的停止，如果一路都大于标记值，那么在到达0索引的时候停止
			while(less(array[start],array[--j])){
				if(j<=0) break;
			}
			
			if(i>=j) break;
			//如果上面两个循环在中途停止了，说明这时需要交换左右两边的值
			exchange(array, i, j);
		}
		//将标记值放到合适的位置，使得左边小于等于它，右边大于等于它
		exchange(array, start, j);
		return j;
	}

}
